package com.hdu.hot100.slideWindow;

import java.util.HashMap;
import java.util.Map;

public class lc76 {
    class Solution {
        public String minWindow(String s, String t) {
            Map<Character, Integer> curWindow = new HashMap<>(), targetWindow = new HashMap<>();
            int curValid = 0, targetValid = 0;
            for (char c : t.toCharArray()) {
                targetWindow.put(c, targetWindow.getOrDefault(c, 0) + 1);
            }
            targetValid = targetWindow.size();
            int start = 0;
            int min = Integer.MAX_VALUE;
            int l = 0, r = 0;
            while (r < s.length())
            {
                char c = s.charAt(r);
                curWindow.put(c, curWindow.getOrDefault(c, 0) + 1);
                if (needChange(curWindow, targetWindow, c)) curValid++;
                while (curValid == targetValid)
                {
                    if (r - l + 1 < min)
                    {
                        min = r - l + 1;
                        start = l;
                    }
                    char lChar = s.charAt(l);
                    if (needChange(curWindow, targetWindow, lChar)) curValid--;
                    if (curWindow.get(lChar) == 1) curWindow.remove(lChar);
                    else curWindow.put(lChar, curWindow.get(lChar) - 1);
                    l++;
                }
                r++;
            }
            return min == Integer.MAX_VALUE ? "" : s.substring(start, start + min);
        }

        boolean needChange(Map<Character, Integer> curWindow, Map<Character, Integer> targetWindow, char curChar)
        {
            return curWindow.get(curChar).equals(targetWindow.get(curChar));
        }
    }
}
